package com.cet.qz.unit01.chapter1_3;

/**
 * @program: algorithm
 * @description: 前移编码
 * @author: 陈恩涛
 * @create: 2021-04-23 22:23
 **/
public class MoveToFront {

    private class Node {
        private char c;
        private Node next;
    }

    private Node first;

    public MoveToFront(String s) {
        int length = s.length();
        for (int i = 0; i < length; i++) {
            Node node = new Node();
            node.c = s.charAt(i);
            if (i == 0) {
                // 插入第一个节点
                first = node;
            } else {
                // 先遍历链表查重，遇到重复节点则删除节点，之后在表头插入该节点
                Node temp = first;
                while (temp.next != null) {
                    if (temp.next.c == node.c) {
                        temp.next = temp.next.next;
                        break;
                    }
                    temp = temp.next;
                }
                node.next = first;
                first = node;
            }
        }
    }

    public MoveToFront() {
    }

    @Override
    public String toString() {
        Node temp = first;
        StringBuilder result = new StringBuilder();
        while (temp != null) {
            result.append(temp.c).append(" ");
            temp = temp.next;
        }
        return result.toString();
    }

    public static void main(String[] args) {
        MoveToFront moveToFront = new MoveToFront("abcdcdefgacdfcsafb");
        System.out.println(moveToFront);
    }
}
